#pragma once
#include<iostream>
#include<assert.h>
using namespace std;


namespace Mango
{
template<class T>
class vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;


    //默认成员函数
    vector() :_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
    {}
    vector(size_t n, const T& val) :_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
    {
        for (int i = 0; i < n; i++)
            push_back(val);
    }
    vector(int n, const T& val) :_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
    {
        for (int i = 0; i < n; i++)
            push_back(val);
    }
    vector(long n, const T& val) :_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
    {
        for (int i = 0; i < n; i++)
            push_back(val);
    }

    template<class InputIterator>
    vector(InputIterator first, InputIterator last)
    {
        while (first != last)
        {
            push_back(*first);
            first++;
        }
    }

    //现代写法1
    vector(vector<T>& v) :_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
    {
        cout << "vector<T>& tmp" << endl;
        vector<T> tmp(v.begin(), v.end());
        swap(tmp);
    }
    
    //现代写法2
#if 0
    vector(const vector<T>& v) :_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
    {
        for (auto& x : v)
            push_back(x);
    }
#endif

    //传统写法
#if 0
    vector(const vector<T>& v) :_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
    {
        _start = new T[v.capacity()];
        _finish = _start;
        _endofstorage = _start + v.capacity();

        for (int i = 0; i < v.size(); i++)
            push_back(v[i]);
    }
#endif

    //现代写法
    vector<T>& operator=(const vector<T>& v)
    {
        if (this != &v)
        {
            vector<T> tmp(v.begin(), v.end());
            swap(tmp);
        }
        return *this;
    }

#if 0
    //传统写法
    vector<T>& operator=(const vector<T>& v)
    {
        if (this != &v)
        {
            delete[] _start;
            _start = new T[v.capacity()];
            _finish = _start + v.size();
            _endofstorage = _start + v.capacity();
            
            for (int i = 0; i < v.size(); i++)
                _start[i] = v[i];
        }
        return *this;
    }
#endif

    ~vector()
    {
        if (_start)
            delete[] _start;
        _start = _finish = _endofstorage = nullptr;//由于三个类型都是一样的，所以可以连续赋值
    }

 ///////////////////////////////////////////////////////////////////////////////
    //移动构造和移动赋值,列表初始化进行初始化
    vector(initializer_list<T>& list):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
    {
        auto it = list.begin();
        while (it != list.end())
        {
            push_back(*it);
            it++;
        }
    }

    vector(vector<T>&& tmp) :_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
    {
        cout << "vector<T>&& tmp" << endl;
        swap(tmp);
    }

    vector<T>& operator=(vector<T>&& tmp)
    {
        if (this != &tmp) //防止v = move(v)
        {
            swap(tmp);
        }
        return *this;
    }

    template<class T>
    void swap(T&& v) //万能引用
    {
        ::swap(_start, v._start);
        ::swap(_endofstorage, v._endofstorage);
        ::swap(_finish, v._finish);
    }
///////////////////////////////////////////////////////////////////////////////

    //迭代器相关函数
    iterator begin()
    {
        return _start;
    }
    iterator end()
    {
        return _finish;
    }

    const_iterator begin()const
    {
        return _start;
    }
    const_iterator end()const
    {
        return _finish;
    }

    //容量和大小相关函数
    size_t size()const
    {
        return _finish - _start;
    }
    size_t capacity()const
    {
        return _endofstorage - _start;
    }
    void reserve(size_t n)
    {
        if (n > capacity()) //确保是扩容
        {
            int sz = size();

            T* tmp = new T[n];
            for (int i = 0; i < size(); i++)
                tmp[i] = _start[i];

            delete[] _start;
            _start = tmp;
            _finish = _start + sz; //注意：需要提前保存原来的元素个数，如果使用size()会计算出错
            _endofstorage = _start + n;
        }
    }

    void resize(size_t n, const T& val = T())
    {
        if (n < size()) //缩小空间
        {
            _finish = _start + n;
        }
        else // n>size()
        {
            if (n > capacity())
                reserve(n);

            for (int i = size(); i < n; i++)
                push_back(val); //如果使用_start[i] = val,最后还需要处理_finish的位置
        }
    }

    bool empty()const
    {
        return _start == nullptr;
    }

    //修改容器内容相关函数
    void push_back(const T& x)
    {
        if (size() == capacity()) //本质上就是：_finish == _endofstorage
            reserve(size() == 0 ? 4 : capacity() * 2);
        
        *_finish++ = x;
    }
    void pop_back()
    {
        assert(empty());
        _finish--;
    }

    void insert(iterator pos, const T& x) //pos位置插入
    {
        //保证pos位置的合法
        assert(pos >= begin() && pos <= end());

        if (size() == capacity())
        {
            int gap = pos - _start;
            reserve(size() == 0 ? 4 : capacity() * 2);
            //大坑：扩容之后_start指向的是新空间,而pos指向的仍然是旧空间的迭代器 
            //所以需要提前保存原来pos的位置,然后扩容之后恢复pos位置
            pos = _start + gap;
        }

        iterator cur = _finish-1;
        while (cur >= pos) //注意：pos位置的元素也要往后移动
        {
            *(cur+1) = *cur;
            cur--;
        }
        *pos = x;
        _finish++;
    }

    iterator erase(iterator pos)
    {
        assert(pos >= begin() && pos < end());

        iterator cur = pos;
        while (cur != end())
        {
            *cur = *(cur+1);
            cur++;
        }
        _finish--;
        return pos;
    }

    

    //访问容器相关函数
    T& operator[](size_t i)
    {
        assert(i < size());
        return _start[i];
    }
    const T& operator[](size_t i)const
    {
        assert(i < size());
        return _start[i];
    }
private:
	iterator _start;
	iterator _endofstorage;
	iterator _finish;
};




void test_vector1()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(6);

    for (size_t i = 0; i < v.size(); ++i)
    {
        cout << v[i] << " ";//1 2 3 4 5 6
    }
    cout << endl;

    vector<int>::iterator it = v.begin();
    while (it != v.end())
    {
        cout << *it << " ";//1 2 3 4 5 6
        ++it;
    }
    cout << endl;

    for (auto e : v)
    {
        cout << e << " ";//1 2 3 4 5 6
    }
    cout << endl;
}


void test_vector3()
{
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    vector<int> v2(v1);
    for (auto e : v2)
        cout << e << " ";//1 2 3 4
    cout << endl;

    vector<int> v3;
    v3.push_back(10);
    v3.push_back(20);
    v3.push_back(30);

    v1 = v3;
    for (auto e : v1)
        cout << e << " ";//10 20 30
    cout << endl;
}

void test_vector4()
{
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    vector<int>::iterator it = find(v1.begin(), v1.end(), 2);
    if (it != v1.end())
    {
        // 如果insert中发生了扩容，那么会导致it指向空间被释放
        // it本质就是一个野指针，这种问题，我们就叫迭代器失效
        v1.insert(it, 20);
    }

    for (auto e : v1)
    {
        cout << e << " ";//1 20 2 3 4
    }
    cout << endl;
}

void test_vector5()
{
    // 三种场景去测试
    // 1 2 3 4 5 -> 正常
    // 1 2 3 4   -> 崩溃
    // 1 2 4 5   -> 没删除完
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(4);
    v1.push_back(5);

    for (auto e : v1)
        cout << e << " "; //1 2 4 5

    // 要求删除v1所有的偶数
    vector<int>::iterator it = v1.begin();
    while (it != v1.end())
    {
        if (*it % 2 == 0)
            it = v1.erase(it);
        else
            ++it;
    }

    for (auto e : v1)
        cout << e << " "; //1 5
    cout << endl;
}

void test_vector6()
{
    vector<string> v;
    v.push_back("111111111111111111111111");
    v.push_back("111111111111111111111111");
    v.push_back("1111111111");
    v.push_back("1111111111");
    v.push_back("1111111111");

    for (auto& e : v)
    {
        cout << e << endl;
    }
    cout << endl;
}
}
